package com.xmg.dataStructure.tensuanfa;

/**
 * 汉诺塔 分治算法
 */
public class Hanoitower {
    public static void main(String[] args) {
        hanoiTower(6,'A','B','C');
    }

    /**
     * 汉诺塔思路分析：
     *     1）只有一个盘 A->C
     *     2）如果有n>=2的情况，总是可以看成两个盘 1、最下面的盘 2、上面的盘
     *         （1）先把最上面的盘 A->B
     *         （2）把最下面的盘A->C
     *         （3）把B塔的盘B->C
     * @param num
     * @param a
     * @param b
     * @param c
     */
    public static void hanoiTower(int num,char a,char b,char c){
        if (num==1){
            System.out.println("第1个盘从"+a+"->"+c);
        }else{
            hanoiTower(num-1,a,c,b);
            System.out.println("第"+num+"个盘从"+a+"->"+c);
            hanoiTower(num-1,b,a,c);
        }
    }
}


